package org.example;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}
class Solution {
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return mergeSort(nums, 0, n - 1);
    }

    private int mergeSort(int[] nums, int l, int r) {
        if(l >= r) return 0;
        int mid = (l + r) >> 1;
        //1.统计左区间(排序好)的个数 + 右区间(排序好)的个数
        int ret = 0;
        ret += mergeSort(nums, l, mid);
        ret += mergeSort(nums, mid + 1, r);

        //2.统计一左一右的个数
        int cur1 = l, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= r){
            if(nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur1++];
            else{
                ret += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
        }

        //3.处理该区间所有元素的排序
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= r) tmp[i++] = nums[cur2++];

        for(int k = l; k <= r; k++) nums[k] = tmp[k - l];
        return ret;
    }
}